package _dp_base;

/**
 * 354. 俄罗斯套娃信封问题
 */
public class No354 {
    private int[][] envelopes;
    private int[] cache;

    /**
     * 1. 递归（会超时）
     */
    public int maxEnvelopes1(int[][] envelopes) {
        this.envelopes = envelopes;
        int n = envelopes.length;
        cache = new int[n];

        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, dfs(i));
        }
        return answer;
    }

    private int dfs(int i) {
        if (cache[i] != 0) return cache[i];
        int curLen = 1;
        for (int j = 0; j < envelopes.length; j++) {
            if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                curLen = Math.max(curLen, dfs(j) + 1);
            }
        }
        return cache[i] = curLen;
    }

    /**
     * 2. 迭代（会超时）
     */
    public int maxEnvelopes2(int[][] envelopes) {
        int n = envelopes.length;
        int[] f = new int[n];

        int answer = 0;
        for (int i = 0; i < n; i++) {
            int curLen = 1;
            for (int j = 0; j < envelopes.length; j++) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    curLen = Math.max(curLen, f[j] + 1);
                }
            }
            f[i] = curLen;
            answer = Math.max(answer, f[i]);
        }

        return answer;
    }
}
